package LearnAlgorithm.f_字符串;

/*
如果一个字符串恰好包含2个h、1个i和1个o，我们就称这个字符串是hiho字符串。
例如haaiaahaao、obbhbbibbhbb都是hiho字符串
现在给定1个只包含小写字母的字符串S,求S的所有子串中最短的hiho字符串是哪个

注意是恰好！必须是严格的2个h、1个i和1个o！！！！！！！！！！！！！！！！！！！！！！！！！！
 */
public class o判断最短hiho字符串 {
	public static void main(String[] args) {
		String s1 = "haaiaahaaohaaiaahaao";
		String s2 = "hhiio";
		chiQuFa(s1.toCharArray());
		chiQuFa(s2.toCharArray());
	}
	
	/**
	 * 尺取法
	 * @param arr
	 */
	public static void chiQuFa(char[] arr) {
		int min = Integer.MAX_VALUE;
		int lastIndex = -1;
		for (int firstIndex = 0; firstIndex < arr.length; firstIndex++) {
			char first = arr[firstIndex];//开始定位目标片段的第一个字符
			if (check(first)) {
				if (lastIndex == -1) {//第一次定位lastIndex
					lastIndex = firstIndex + 1;
				}
				while (lastIndex < arr.length) {//开始定位目标片段的最后一个字符
					char last = arr[lastIndex];
					if (check(last) && containsAll(arr, firstIndex, lastIndex)) {//last符合hio标准并且当前片段[firstIndex,lastIndex]包含制定规则的字符
						if (check(arr, firstIndex, lastIndex) && lastIndex - firstIndex + 1 < min) {//当前片段[firstIndex,lastIndex]严格符合2h1i1o；片段长度小于历史最小
							min = lastIndex - firstIndex + 1;//更新历史最小片段长度
						}
						break;//终止寻找last
					}
					lastIndex++;//不符合hio;不包含符合规则全部字符;向后推进lastIndex指针
				}
			}
		}
		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
	}
	
	/**
	 * 严格判断判断字符片段是否包含2h1i1o
	 * @param arr
	 * @param i
	 * @param j
	 * @return
	 */
	public static boolean check(char[] arr, int i, int j) {
		int charH = 0;
		int charI = 0;
		int charO = 0;
		for (int k = i; k <= j; k++) {
			if (arr[k] == 'h') {
				charH++;
			}
			if (arr[k] == 'i') {
				charI++;
			}
			if (arr[k] == 'o') {
				charO++;
			}
		}
		return charH == 2 && charI == 1 && charO == 1;
	}
	
	/**
	 * 判断字符是不是h或者i或者o
	 * @param c
	 * @return
	 */
	public static boolean check(char c) {
		return c == 'h' || c == 'i' || c == 'o';
	}
	
	/**
	 * 判断字符片段包含
	 * h >=2个
	 * i >=1个
	 * o >=1个
	 * @param arr
	 * @param i
	 * @param j
	 * @return
	 */
	public static boolean containsAll(char[] arr, int i, int j) {
		int charH = 0;
		int charI = 0;
		int charO = 0;
		for (int k = i; k <= j; k++) {
			if (arr[k] == 'h') {
				charH++;
			}
			if (arr[k] == 'i') {
				charI++;
			}
			if (arr[k] == 'o') {
				charO++;
			}
		}
		return charH >= 2 && charI >= 1 && charO >= 1;
	}
}
